package com.njupt.StackAndQueue;

import java.util.*;
import java.util.stream.Stream;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/17 15:45
 * @Description: 239 滑动窗口最大值
 * @Version: 1.0
 */


public class MaxSlidingWindow {

    /**
     * 暴力法
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        List<Integer> integers = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();


        for (int i = 0; i < nums.length; i++) {
            if(queue.size() == k){
                Optional<Integer> maxElement  = queue.stream().max((num1, num2) -> {
                    return num1 - num2;
                });
                integers.add(maxElement.get());
                queue.removeFirst();
                queue.addLast(nums[i]);
            }else {
                queue.addLast(nums[i]);

            }
        }
        if(queue.size() == k){
            Optional<Integer> maxElement  = queue.stream().max((num1, num2) -> {
                return num1 - num2;
            });
            integers.add(maxElement.get());
        }

        int[] result = new int[integers.size()];
        Iterator<Integer> iterator = integers.iterator();
        int index = 0;
        while(iterator.hasNext()){
            result[index++] = iterator.next();
        }

        return result;
    }

    /**
     * 暴力法 改进
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow1(int[] nums, int k){
        List<Integer> integers = new ArrayList<>();
        Deque<Integer> queue = new LinkedList<>();


        for (int i = 0; i < nums.length; i++) {
           queue.addLast(nums[i]);
           if(queue.size() == k){
               Optional<Integer> maxElement = queue.stream().max((num1, num2) -> {
                   return num1 - num2;
               });
               integers.add(maxElement.get());
               queue.removeFirst();
           }
        }


        int[] result = new int[integers.size()];
        Iterator<Integer> iterator = integers.iterator();
        int index = 0;
        while(iterator.hasNext()){
            result[index++] = iterator.next();
        }

        return result;
    }

    /**
     * 法二：单调队列
     *
     * 这里定义单调递减的队列
     * 保证了每次添加一个元素，删除一个元素都保证时单调递减的
     */
    class MonotonicQueue{
        Deque<Integer> monotonicQueue = new LinkedList<>();

        //往单调递减队列中添加元素，如果要添加的元素大于入口元素，那就将入口元素弹出。
        public void addLast(int value){
            while(!monotonicQueue.isEmpty() && value> monotonicQueue.getLast()){
//                monotonicQueue.removeFirst();
                monotonicQueue.removeLast();
            }

            monotonicQueue.addLast(value);
        }

        //弹出元素时，比较当前要弹出的值是否等于队列出口的值，如果等于则弹出
        public void removeFirst(int value){
            if(!monotonicQueue.isEmpty() && value == monotonicQueue.peekFirst()){
                monotonicQueue.removeFirst();
            }
        }

        //队列对顶元素始终为最大值
        int peek(){
            return monotonicQueue.peekFirst();
        }

    }

    public int[] maxSlidingWindow2(int[] nums, int k){
        List<Integer> integers = new ArrayList<>();
        MonotonicQueue monotonicQueue = new MonotonicQueue();
        for (int i = 0; i < k; i++) {
            monotonicQueue.addLast(nums[i]);
        }
        integers.add(monotonicQueue.peek());
        for (int i = k; i < nums.length ; i++) {
            monotonicQueue.removeFirst(nums[i-k]);
            monotonicQueue.addLast(nums[i]);
            integers.add(monotonicQueue.peek());
        }

        return integers.stream().mapToInt(Integer::intValue).toArray();
        
    }

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        MaxSlidingWindow test = new MaxSlidingWindow();
        int[] ints = test.maxSlidingWindow2(nums, 3);
        System.out.println(Arrays.toString(ints));
    }
}
